package com.gaofeng.algo.java;

import java.util.*;

public class BacktrackJava {

    public static void main(String[] args) {
        BacktrackJava demo = new BacktrackJava();
        int[] numbers = new int[]{1, 2, 3};
        demo.permute2(numbers);
    }

    private int m, n;
    private int[] direction = new int[]{-1, 0, 1, 0, -1};

    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) {
            return false;
        }
        m = board.length;
        n = board[0].length;
        boolean[][] marked = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //从任意一个顶点进行搜索,如果搜到,就返回true
                if (backtrackWord(board, word, i, j, 0, marked)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && y >= 0 && x < m && y < n;
    }

    private boolean backtrackWord(char[][] board, String word, int i, int j, int position, boolean[][] marked) {
        //从单词的第一个位置开始搜索,如果搜到最后一个位置,就判断当前的顶点是否与单词的最后一个字符相等
        if (position == word.length() - 1) {
            return board[i][j] == word.charAt(position);
        }
        //如果当前顶点是与单词匹配的,就进行下一次的搜索.所以位置
        if (board[i][j] == word.charAt(position)) {
            //将其标注为搜过的,回退的状态是当前顶点在深搜的过程中,是否被标记过
            marked[i][j] = true;
            //判断下一个方向.
            for (int k = 0; k < 4; k++) {
                int newX = i + direction[k];
                int newY = j + direction[k + 1];
                //新的顶点要在区间内,并且没有被搜索过.
                if (inArea(newX, newY) && !marked[newX][newY]) {
                    //将单词搜索的位置往后挪一位,并且新的顶点位置开始递归搜索
                    if (backtrackWord(board, word, newX, newY, position + 1, marked)) {
                        return true;
                    }
                }
            }
            //回退标记状态,当前顶点是否被搜索过.
            marked[i][j] = false;
        }
        return false;
    }


    public List<List<Integer>> permute2(int[] nums) {
        int size = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        if (size == 0) {
            return ans;
        }
        boolean[] used = new boolean[size];
        Deque<Integer> path = new ArrayDeque<>(size);
        backtrack2(used, ans, path, size, 0, nums);
        return ans;
    }

    private void backtrack2(boolean[] used, List<List<Integer>> ans, Deque<Integer> path, int size, int depth, int[] numbers) {
        if (depth == size) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < size; i++) {
            if (!used[i]) {
                used[i] = true;
                path.addLast(numbers[i]);
                backtrack2(used, ans, path, size, depth + 1, numbers);
                used[i] = false;
                path.removeLast();
            }
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        List<Integer> output = new ArrayList<>();
        for (int num : nums) {
            output.add(num);
        }
        int n = nums.length;
        backtrack(n, answer, output, 0);
        return answer;
    }

    private void backtrack(int n, List<List<Integer>> ans, List<Integer> output, int first) {
        //结束条件,遍历完了就将遍历的输入过程的状态值添加到最终的输出结果中
        if (first == n) {
            ans.add(new ArrayList<>(output));
            return;
        }
        for (int i = first; i < n; i++) {
            //从第first个位置开始,首先和剩下的元素交换
            Collections.swap(output, i, first);
            //然后执行递归方法
            backtrack(n, ans, output, first + 1);
            //在把状态还原
            Collections.swap(output, i, first);
        }
    }


    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        // 从 1 开始是题目的设定
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        // 递归终止条件是：path 的长度等于 k
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 遍历可能的搜索起点
        for (int i = begin; i <= n; i++) {
            // 向路径变量里添加一个数
            path.addLast(i);
            // 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            // 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
            path.removeLast();
        }
    }
}
